This invention relates to registration of digital images.
Procedures for registration of images are used in a variety of applications. In one application an area of interest is tracked in an image sequence, such as in a sequence of video frames, by locating the area in each successive frame. The tracking results are used, for example, to stabilize a hand-held video by translating each frame to stabilize the motion of the area of interest. In one such application, an initial area to track is identified in the first image of the sequence. This initial area forms a template that is located within the next image in the sequence using a registration procedure. The template is then optionally updated in appearance based on its location in that next image, and the process is repeated for each subsequent image in the sequence. The search region for the template in a given image is typically restricted to locations near the template's location in the previous image in the sequence.
For some applications of tracking, such as for video stabilization discussed above, a location estimate that is accurate only to the nearest pixel may result in poorer quality than if the registration of the template within each image is allowed to fall at a fractional pixel location. This is due, at least in part, to the aptitude of the human eye at detecting even very small changes in position.
Registration has other applications, such as adding special effects to video. To draw attention to particular moving feature in a video a marker, such as a synthetic arrow, can be drawn at a fixed offset from the feature in each of a sequence of video frames. A template of the feature is registered with each image in the video to determine where to draw the marker. As in the image stabilization application, a viewer may notice the small deviations or jitter of the marker particularly if the feature is moving in a regular motion such as along a straight line.
One prior method for sub-pixel accurate image registration makes use of an iterative approach to determine the registration of a template of a region of interest and an image. At each step in the iteration, this approach requires computing interpolated values at non-pixel locations in the image and computing approximations of spatial gradients at those locations. Based on the interpolated values and the spatial gradients, a next approximation of the registration location in the iteration is computed, for example, using a Newton-Raphson iteration. The iteration is then allowed to converge, or is terminated prior to convergence, to yield the sub-pixel registration location.